Sau khi Chiến tranh Thế giới thứ hai chấm dứt, Quân đội Viễn chinh Pháp trở sang Đông Dương đem theo một lực lượng hùng hậu chiếm đóng ba xứ Việt, Miên, Lào, nhằm đặt lại nền đô hộ trên các thuộc địa cũ theo chính sách thực dân của Pháp. Tướng Charles de Gaulle bổ nhiệm đô đốc Thierry d'Argenlieu làm Cao ủy Đông Dương và tướng Philippe Leclerc de Hauteclocque làm Tư lệnh Quân đội Viễn chinh. Vào cuối tháng 9 năm 1945, quân đội Pháp đã núp bóng quân đội Anh do tướng Douglas Gracey chỉ huy để giải giới Quân đội Nhật từ vĩ tuyến 16 trở xuống.

Cuộc xâm lăng mới của Pháp này đã gặp sức kháng cự mạnh mẽ của Việt Nam, nhất là Chính phủ Việt Nam Dân chủ Cộng hòa, các đoàn thể võ trang như Cao Đài, Hòa Hảo, Bình Xuyên trong Miền Nam.

Mặc dù tinh thần kháng chiến chống thực dân của người Việt rất cao, nhưng vì vũ khí thô sơ và tổ chức còn rời rạc, nên các lực lượng vũ trang này bị quân Pháp đánh bật khỏi các đô thị ven biển và đồng bằng. Đa số phải rút về thôn quê hay vào bưng biền để tổ chức trường kỳ kháng chiến. Pháp nhanh chóng tổ chức các lực lượng bản xứ để trợ giúp cho việc chiếm đóng và bình định lãnh thổ.

Trong số những người ra cộng tác với Pháp, một số đã gia nhập Quân đội Viễn chinh và được gọi là Thân binh Đông Dương (Partisans Indochinois). Về sau, vì nhu cầu chiến tranh bành trướng mau lẹ, người Pháp đã tuyển mộ lính địa phương tại chỗ và lập thành các lực lượng phụ thuộc (forces suppletives) do sĩ quan Pháp chỉ huy. Nhiều người hợp tác với Pháp là các phần tử muốn nhờ cậy vào thế lực của Pháp để chống lại Việt Minh, phong trào mà họ cho là có xu hướng thân Chủ nghĩa Cộng sản.

Sang năm 1948, "Giải pháp Bảo Đại" ra đời với chủ trương đoàn kết các lực lượng chống Việt Minh. Theo Hiệp ước Élysée ký ngày 8 tháng 3 năm 1949 giữa Quốc trưởng Việt Nam Bảo Đại và Tổng thống Pháp Vincent Auriol, Quốc gia Việt Nam được thành lập, có Quân đội và Chính sách ngoại giao riêng. Do đó, quân đội được chính thức thành lập và lấy tên là Quân đội Quốc gia Việt Nam.

Do nghị định Quốc phòng ngày 13 tháng 4 năm 1949, Quân đội Quốc gia được thành lập, lúc đầu lấy tên là Vệ binh Quốc gia (Garde Nationale). Quân đội Quốc gia lúc này có quy chế riêng và lương bổng được hưởng tương đối cao hơn phụ lực quân lúc trước. Ba đơn vị chiến đấu đầu tiên được thành lập ngày 1 tháng 10 năm 1949 là các Tiểu đoàn Bộ binh số 18, 2 và 3, gọi tắt là BVN (Batallion Vietnamien).

Lần lượt, các lực lượng quân sự phụ thuộc khác như Cộng hòa Vệ binh trong Nam, Bảo vệ Quân ở Miền Trung (sau đổi tên là Việt binh Đoàn) và Bảo chính Đoàn ở Bắc, v.v... được thuyên chuyển qua hoặc sáp nhập vào Quân đội Quốc gia. Còn các lực lượng võ trang của các Giáo phái như Cao Đài, Hòa Hảo, Bình Xuyên tại Miền Nam Việt Nam hoặc trở về hợp tác với Chính phủ Quốc gia Việt Nam, hoặc rút vào bưng, nhưng sau đó cũng bị tiêu diệt lần hồi.

Quân số Quân đội Quốc gia vào cuối năm 1949 là 45.000 người, không kể các lực lượng còn trong hệ thống quân đội Pháp.

Ngày 11 tháng 5 năm 1950, Thủ tướng Trần Văn Hữu tuyên bố thành lập Quân đội Quốc gia với lập trường "Chống Cộng", gia tăng quân số lên 60.000 người, do ngân sách Quốc gia đài thọ 40%, phần còn lại do Pháp gánh chịu. Viện trợ Mỹ cũng bắt đầu giao thẳng cho các đơn vị Việt Nam, chứ không qua trung gian Quân đội Pháp theo Chương trình Viện trợ Hỗ tương Quốc phòng (Mutual Defense Assistance Program - MDAP).

Ngày 5 tháng 5 năm 1951, Bộ Quốc phòng Việt Nam mới thật sự thành hình, với những cơ cấu tổ chức đầu não như Bộ Tổng tham mưu, Nha Quân pháp, Nha Thanh tra, Tổng nha Hành chánh và Quân lương, Nha Quân cụ, Nha Quân y, v.v.

Cuối năm 1951, quân số lên tới 110.000 người. Các đơn vị nòng cốt được thành lập trong thời kỳ này là:
-Tiểu đoàn Nhảy dù.
-Đại đội 1 và 3 Truyền tin.
-Đệ Nhất Chi đoàn Thám thính xa.
-Tiểu đoàn Pháo binh.
-Đại đội 2 và 3 Công binh.

Cuối năm 1952, Quân đội Quốc gia có 148.000 người, gồm 95.000 quân Chủ lực và 53.000 Bảo an Địa phương. Các đơn vị gồm có:
-59 Tiểu đoàn Bộ binh.
-2 Tiểu đoàn Nhảy dù.
-2 Tiểu đoàn Ngự lâm quân.
-8 Tiểu đoàn Sơn cước

Về cơ giới có:
-6 Chi đoàn Thám thính xa.
-1 Tiểu đoàn Pháo binh và 8 Pháo đội biệt lập.
-6 Đại đội Vận tải.
-6 Đại đội Truyền tin.
-2 Liên đoàn Tuần giang.

Năm 1954, Quân đội Quốc gia có nhiều Tiểu đoàn tham gia trận Điện Biên Phủ bên cạnh lực lượng Pháp. Một chỉ huy nổi tiếng là một sĩ quan người Việt, Phạm Văn Phú (sau này là Tư lệnh Quân đoàn của Quân lực Việt Nam Cộng hòa) và nhiều đơn vị tiêu biểu cũng tham gia trận đánh, gây nhiều khó khăn cho bộ đội Việt Minh. Tổng số quân nhân người Việt ở lòng chảo Mường Thanh khoảng 2.000 binh sĩ. Pháp thất bại sau 55 ngày đêm chiến đấu, tất cả quân nhân Pháp và Việt chịu chung số phận bị Việt Minh bắt sống.